反素数

题目链接:https://www.acwing.com/problem/content/description/200/
题目大意:对于任何的正整数x,定义g(x)=xg(x) = x的约数个数。若对于任意的i<xi<x都有g(i)<g(x)g(i) < g(x)则称xx为反素数。现给定一个整数N(1N2109)N(1 \leq N \leq 2*10^9),求不超过N的最大的反素数是多少。

分析

首先NN的范围非常大,想要筛质数或者筛约数的方法肯定都做不了,顶多就对某个数筛一次,因此题目肯定有什么隐含的能够降低答案查找范围的条件没有挖掘出来。
性质1:1N1到N中最大的反素数,就是范围内约数最多且最大的数。
证明:若xx是反素数,则xx需要满足:

{i<m,g(i)<g(x)i>m,g(i)g(x)\begin{cases}\forall i < m,g(i)< g(x)\\ \forall i > m,g(i) \leq g(x) \end{cases}

性质2:1N1到N中任何数的不同的质因子都不会超过10个,且所有质因子指数的总和不超过30
证明:最小的1010个质因子乘起来就已经超范围了,最小的质因子2302^{30}也会超范围。

至此我们已经把范围缩小到所求的质因子不超过10个,且指数控制在了一个有限的范围内,但这些条件还不足以去搜索,因为根本没法筛这么大范围的素数,肯定不行,还需要想办法缩小枚举的数的范围,和指数的范围。

性质3:最终答案的质因子只包括最小的前十个质因子,且指数呈下降趋势。
也就是说质因子只有2,3,,5,7,11,13,17,19,23,29{2,3,,5,7,11,13,17,19,23,29}这些数,且他们的指数c1c2...c100c_1 \geq c_2 \geq ... \geq c_{10} \geq 0
证明:假设有一个质因子pk(p>29)p^k(p > 29),则原来的答案xx中一定存在一个pp'满足p<=29p' <= 29,且不整除xx,但是我们可以构造出一个x=x/pkpkx' = x / {p^k} * {p'^k},由于约数的个数仅与指数有关,而新构造出来的xx'显然又小于原来的答案,故xx不应该是一个反素数,矛盾。
其次,假设xx里的两个质因子分别是p1c1p_1^{c_1}p2c2p_2^{c_2},且c1<c2c1<c2
如果我们把指数交换,同样可以构造出一个新的答案满足约数个数一致,但新的答案更大。因此我们可以构造出一个比原来答案更大的反素数,因此矛盾。

综上所述,我们可以做一个DFS搜索确定前十个数的指数和约数的个数,并更新答案。

代码 https://www.acwing.com/activity/content/code/content/357942/